package com.lbt.javaSE.sort;

import java.util.HashMap;
import java.util.Map;
import java.util.jar.JarOutputStream;

//稳定的计数排序 时间复杂度为  O(n) 空间占用比较多 2倍数
public class JishuPaixu {


    public static void SortJS(int[] nums){
        int min=nums[0],max=nums[0];
        for(int a: nums){
            min=(min>a?a:min);
            max=(max<a?a:max);
        }
//        System.out.println("MAX__"+max+"MIN__"+min);
        int numbers[]=new int[max-min+1];
//        System.out.println("numbers长度:__"+numbers.length);

        for(int i=0;i<nums.length;i++){

            int index1=nums[i]-min;
            numbers[index1]++;
//           System.out.println("i:___"+i+"index:___"+index1+"__number__"+numbers[index1]);
        }
        for(int i=1;i<numbers.length;i++){
            numbers[i]+=numbers[i-1];
        }
        int result[]=new int[nums.length];
        int index=nums.length-1;
//        System.err.println("NUms__"+nums[index]);
        while(index>=0){

            int index2=nums[index]-min; //数字在number 中的位置
//            System.out.println("Index2__"+index2);

            int index3=numbers[index2];
//            System.err.println("**********************index3__"+index3);

//            System.out.println("Number_index__:"+index2);
//            System.err.println("Index3__"+index3);
            result[index3-1]=nums[index];
            numbers[index2]--;
//            System.out.println("位置index__"+index3+"大小number__"+nums[index]);
            index--;
        }
        for(int re:result){
            System.out.print(re);
        }
    }

    public static void main(String[] args) {
        int[] nums=new int[]{0,1,2,3,4,5,6};
        HashMap<String,String>map=new HashMap<>();

        SortJS(nums);
    }
}
